import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Util {
	public static long factorial(long n) {
		long r = 1;
		for (int i = 2; i <= n; i++) {
			r *= i;
		}
		return r;
	}
	
	public static String reverse(String x) {
		return new StringBuffer(x).reverse().toString();
	}
	
	public static String reverse(BigInteger x) {
		return reverse(x.toString());
	}
	
	public static boolean isPalindromic(BigInteger x) {
		return x.toString().equals(reverse(x.toString()));		
	}	
	
	public static List<Long> primeList(long n) {
		List<Long> primeList = new ArrayList<Long>();
		for (long i = 2; i < n; i++) {
			if (isPrime(i)) {
				primeList.add(i);	
			}
		}
		return primeList;
	}
	
	public static boolean isPrime(long n) {
		if (n < 2) {
			return false;
		}

		long max = (long) Math.sqrt(n);
		for (long i = 2; i <= max; i++) {
			if (n % i == 0) {
				return false;
			}
		}

		return true;
	}

	public static boolean isPrime(long n, List<Integer> primeList) {
		if (n < 2) {
			return false;
		}

		for (Integer p : primeList) {
			if (n % p == 0) {
				return false;
			}
		}

		return true;
	}
	
	public static boolean isPrime2(long n) {
	    if(n < 2) return false;
	    if(n == 2 || n == 3) return true;
	    if(n%2 == 0 || n%3 == 0) return false;
	    long sqrtN = (long)Math.sqrt(n)+1;
	    for(long i = 6L; i <= sqrtN; i += 6) {
	        if(n%(i-1) == 0 || n%(i+1) == 0) return false;
	    }
	    return true;
	}
	
	public static Map<Long, Long> primeFactor(long num) {
		long n = (long) Math.ceil(Math.sqrt(num));
		Map<Long, Long> map = new HashMap<Long, Long>();
		boolean hasPrimeFactor = false;

		for (long i = 2; i <= n; i++) {
			while (num % i == 0) {
				hasPrimeFactor = true;
				Long x = map.get(i);
				if (x == null) {
					x = 0L;
				}
				map.put(i, ++x);
				num /= i;
				n = num;
			}
		}

		if (!hasPrimeFactor) {
			map.put(num, 1L);
		}
		return map;
	}
	
	public static List<Long> primeFactor2(long num) {
		long n = (long) Math.ceil(Math.sqrt(num));
		List<Long> list = new ArrayList<Long>();
		
		for (long i = 2; i <= n; i++) {
			while (num % i == 0) {				
				if (!list.contains(i)) {
					list.add(i);
				}
				num /= i;
				n = num;
			}
		}

		if (list.size() == 0) {
			list.add(num);
		}
		return list;
	}

	public static void getPermutationList(List<Long> list, String num, String result) {
		if (num.length() == 0) {
			long x = Long.parseLong(result);
			list.add(x);
			return;
		}

		for (int i = 0; i < num.length(); i++) {
			String n = num.substring(i, i + 1);
			getPermutationList(list, num.substring(0, i) + num.substring(i + 1), result + n);
		}
	}

	public static List<Long> getPermutationList(String num) {
		List<Long> list = new ArrayList<Long>();
		getPermutationList(list, num, "");
		return list;
	}
	
	public static void getCombinationList(List<Long> list, String num, String result, int index, int size) {
		if (result.length() == size) {
			long x = Long.parseLong(result);
			list.add(x);
			return;
		}

		for (int i = index; i < num.length(); i++) {
			String n = num.substring(i, i + 1);
			getCombinationList(list, num, result + n, i + 1, size);
		}
	}

	public static List<Long> getCombinationList(String num, int size) {
		List<Long> list = new ArrayList<Long>();
		getCombinationList(list, num, "", 0, size);
		return list;
	}
	
	public static <T> void getCombinationSet(Set<List<T>> set, List<T> itemList, List<T> resultList, int index, int size) {
		if (resultList.size() == size) {
			set.add(resultList);
			return;
		}

		for (int i = index; i < itemList.size(); i++) {
			List<T> tempList = new ArrayList<T>(resultList);
			tempList.add(itemList.get(i));
			getCombinationSet(set, itemList, tempList, i + 1, size);
		}
	}

	
	public static <T> Set<List<T>> getCombinationSet(List<T> list, int size) {
		Set<List<T>> set = new LinkedHashSet<List<T>>();
		getCombinationSet(set, list, new ArrayList<T>(), 0, size);
		return set;
	}
	
	public static <T> void getCombinationSet(Set<List<T>> set, List<T> itemList, List<T> resultList, int index, int size, T incluedObject) {
		if (resultList.size() == size) {
			if (resultList.contains(incluedObject)) {
				set.add(resultList);
			}
			return;
		}

		for (int i = index; i < itemList.size(); i++) {
			List<T> tempList = new ArrayList<T>(resultList);
			tempList.add(itemList.get(i));
			getCombinationSet(set, itemList, tempList, i + 1, size, incluedObject);
		}
	}
	
	public static <T> Set<List<T>> getCombinationSet(List<T> list, int size, T includedObject) {
		Set<List<T>> set = new LinkedHashSet<List<T>>();
		getCombinationSet(set, list, new ArrayList<T>(), 0, size, includedObject);
		return set;
	}
	
	public static <T> void getCombinationSet2(Set<List<T>> set, List<T> itemList, List<T> resultList, int index, int size) {
		if (resultList.size() == size - 1) {
			resultList.add(itemList.get(itemList.size() - 1));
			set.add(resultList);
			return;
		}

		for (int i = index; i < itemList.size() - 1; i++) {
			List<T> tempList = new ArrayList<T>(resultList);
			tempList.add(itemList.get(i));
			getCombinationSet2(set, itemList, tempList, i + 1, size);
		}
	}
	
	public static <T> Set<List<T>> getCombinationSet2(List<T> list, int size) {
		Set<List<T>> set = new LinkedHashSet<List<T>>();
		getCombinationSet2(set, list, new ArrayList<T>(), 0, size);
		return set;
	}
	
	public static Set<Long> getPermutationSet(String num) {
		List<Long> list = getPermutationList(num);
		return new HashSet<Long>(list);
	}
	
	public static boolean isPermuation(long... n) {
		Set<Long> set = getPermutationSet(String.valueOf(n[0]));
		for (int i = 1; i < n.length; i++) {
			if (!set.contains(n[i])) {
				return false;
			}
		}
		
		return true;
	}
	
	public static long[] addFraction(long a, long b, long c, long d) {
		long numerator = a * d + c * b;
		long denominator = b * d;
		//System.out.println(numerator + "/" + denominator);
		//return reduce(numerator, denominator);		
		return new long[] {numerator, denominator};
	}
	
	public static int normalize(Map<Long, Long> m) {
		
		Iterator<Long> iterator = m.keySet().iterator();
		int sum = 1;
		while (iterator.hasNext()) {
			long prime = iterator.next();
			sum *= Math.pow(prime, m.get(prime));
		}
		
		return sum;
	}
	
	private static Map<Long, Map<Long, Long>> primeFactorMap = new HashMap<Long, Map<Long, Long>>();
	
	public static long[] reduce(long a, long b) {
		Map<Long, Long> p1 = new HashMap<Long, Long>(getCachedPrimeFactor(a));
		Map<Long, Long> p2 = new HashMap<Long, Long>(getCachedPrimeFactor(b));
		
		Long[] primes = p1.keySet().toArray(new Long[0]);
		for (long i = 0; i < primes.length; i++) {
			Long prime = primes[(int)i];
			Long count1 = p1.get(prime);
			
			if (p2.containsKey(prime)) {
				Long count2 = p2.get(prime);
				
				long min = Math.min(count1, count2);
				
				if (count1 - min == 0) {
					p1.remove(prime);
				} else {
					p1.put(prime, count1 - min);
				}
				
				if (count2 - min == 0) {
					p2.remove(prime);
				} else {
					p2.put(prime, count2 - min);
				}
			}
		}
		
		return new long[] {normalize(p1), normalize(p2)};
	}

	private static Map<Long, Long> getCachedPrimeFactor(long a) {
		Map<Long, Long> primeFactor = primeFactorMap.get(a);
		if (primeFactor == null) {
			primeFactor = primeFactor(a);
			primeFactorMap.put(a, primeFactor);
		}
		return primeFactor;
	}
	
	public static void main(String[] args) {
		List<Integer> sampleList = new ArrayList<Integer>();
		sampleList.add(1);
		sampleList.add(2);
		sampleList.add(3);
		sampleList.add(4);		
		System.out.println(getCombinationSet(sampleList, 3));
		System.out.println();
		
		
		System.out.println(getCombinationList("1234", 3));
		System.out.println();
		
		System.out.println(Arrays.toString(addFraction(2, 1, 2, 5)));
		System.out.println(Arrays.toString(addFraction(120, 90, 2, 3)));
		System.out.println(Arrays.toString(reduce(120, 90)));
		System.out.println(primeFactor(2));
		System.out.println(primeFactor(3));
		System.out.println(primeFactor(17));
		System.out.println(primeFactor(32));
		System.out.println(primeFactor(41));
		
		List<Long> list = getPermutationList("1223");
				
		for (Long n : list) {
			System.out.println(n);
		}
		
		System.out.println();
		list = getPermutationList("123");
		
		for (Long n : list) {
			System.out.println(n);
		}
		
		System.out.println(isPermuation(123, 231));
		System.out.println(isPermuation(123, 345));
	}
	
	public static Map<Long, Long> getPrimeFactor(long num) {
		Map<Long, Long> primeFactors = new LinkedHashMap<Long, Long>();
		
		long sqrt = (long) Math.sqrt(num);
		
		for (long i = 2; i <= sqrt; i++) {
			long power = 0;
			while (num % i == 0) {
				power++;
				num /= i;
				primeFactors.put(i, power);
			}
		}
		
		if (num != 1) {
			primeFactors.put(num, 1L);
		}
		
		return primeFactors;
	}
	
	public static int getDivisorCount(long num) {
		if (num == 1) {
			return 1;
		}
		
		if (num < 1) {
			return 0;
		}
		
		Map<Long, Long> primeFactors = getPrimeFactor(num);
		Long[] prime = primeFactors.keySet().toArray(new Long[0]);
		int divisorCount = 1;
		for (int i = 0; i < prime.length; i++) {
			divisorCount *= (primeFactors.get(prime[i]) + 1);
		}
		return divisorCount;
	}
	
	
	
	public static String factorial(String a) {
		String factorial = "1";
		String count = "1";
		while (!count.equals(a)) {
			factorial = product(factorial, count);
			count = sum(count, "1");
		}
		factorial = product(factorial, a);
		return factorial;
	}
	
	public static int compare(String a, String b) {
		if (a.length() > b.length()) {
			return 1;
		} else if (a.length() < b.length()) {
			return -1;
		} else {
			if (a.equals(b)) {
				return 0;
			}
			
			byte[] aByte = a.getBytes();
			byte[] bByte = b.getBytes();
			
			for (int i = 0; i < aByte.length; i++) {
				if (aByte[i] > bByte[i]) {
					return 1;
				} else if (aByte[i] < bByte[i]) {
					return -1;
				}
			}
			return 0;
		}
	}
	
	public static String quota(String a, String b) {
		String quota = "0";
		String denominator = b;
		
		if (compare(a, b) == 0) {
			quota = "1";
		} else {
			while (compare(a, denominator) > 0) {
				denominator = sum(denominator, b);
				quota = sum(quota, "1");
			}
		}
		
		return quota;
	}
	
	
	public static String minus(String big, String small) {
		if (big.equals(small)) {
			return "0";
		}
		
		String minus = "0";
		
		while(!small.equals(big)) {
			small = sum(small, "1");
			minus = sum(minus, "1");
		}
		
		return minus;
	}
	
	public static String divide(String a, String b, long size) {
		String result = "";
		
		if (compare(a, b) == 0) {
			return "1";
		}
		
		if (compare(a, b) > 0) {
			result = quota(a, b);
			a = minus(a, product(b, result));
			result += ".";
		}
		
		System.out.println(a);
		System.out.println(result);
		
		if (compare(a, b) < 0) {
			a += "0";
			result = ".";
		}
		
		while (compare(a, b) < 0) {
			result += "0";
			a += "0";
		}
		
		
		while (true) {
			System.out.println(a + ", " + b);
			if (compare(a, b) >= 0) {
				String quota = quota(a, b);
				result += quota;
				String reamin = minus(a, product(b, quota));
				if (reamin.equals("0")) {
					break;
				} else {
					a += "0";
				}
			}
			
			if (compare(a, b) < 0) {
				result += "0";
				a += "0";
			}
			
			int index = result.indexOf(".");
			if (index > 0) {
				if (size < result.length() - index) {
					break;
				}
			}
			break;
		}
		
		return result;
	}
	
	public static String power(String a, String b) {
		String power = a;
		String count = "1";
		while (!count.equals(b)) {
			power = product(power, a);
			count = sum(count, "1");
		}
		return power;
	}
	
	public static String product(String a, String b) {
		String sum = "0";
		String count = "0";
		while (!count.equals(b)) {
			sum = sum(sum, a);
			count = sum(count, "1");
		}
		return sum;
	}
	
	public static String sum(String a, String b) {
		int maxLength = Math.max(a.length(), b.length());
		a = appendZero(a, maxLength);
		b = appendZero(b, maxLength);
	
		byte[] aBytes = getDigit(a);
		byte[] bBytes = getDigit(b);
		
		byte[] result = new byte[maxLength];
		int hasExtra = 0;
		
		for (int i = maxLength - 1; i >= 0; i--) {
			byte sum = 0;
			if (i < aBytes.length) {
				sum += aBytes[i];
			}
			
			if (i < bBytes.length) {
				sum += bBytes[i];
			}
			
			sum += hasExtra;
			
			hasExtra = sum/10;
			result[i] = (byte) (sum%10); 
		}
		
		for (int i = 0; i < result.length; i++) {
			result[i] += 48;
		}
		
		String c = (hasExtra > 0 ? String.valueOf(hasExtra): "") + new String(result);
		return c;
	}
	
	public static byte[] getDigit(String text) {
		byte[] a = text.getBytes();
		for (int i = 0; i < a.length; i++) {
			a[i] -= 48;
		}
		return a;
	}
	
	public static String appendZero(String a, int length) {
		String result = "";
		for (int i = 0; i < length - a.length(); i++) {
			result += "0";
		}
		result += a;
		return result;
	}
	
	public static String getNumber(byte[] a) {
		for (int i = 0; i < a.length; i++) {
			a[i] += 48;
		}
		return new String(a);
	}
	
	public static void printByte(byte[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]);
			System.out.print(" ");
		}
	}
	
	
	public static String getContent(File f) {
		return getContent(f, false);		
	}
	
	public static int sumOfDigit(String result) {
		byte[] b = result.getBytes();
		int sum = 0;
		for (int i = 0; i < b.length; i++) {
			sum += (b[i] - 48);
		}
		return sum;
	}
	
	public static String getContent(File f, boolean appendNewLine) {
		StringBuffer buffer = new StringBuffer();
		BufferedReader reader = null;
		try {
			reader = new BufferedReader(new InputStreamReader(new FileInputStream(f)));
			String line = null;
			while((line = reader.readLine()) != null) {
				buffer.append(line);
				buffer.append("\n");
			}
		} catch (Exception e) {
			// TODO: handle exception
		} finally {
			if (reader != null) {
				try {
					reader.close();
				} catch (Exception e) {
				}
			}
		}
		return buffer.toString();
	}
	
	public static long isSqure(long n) {
		long squre = (long) Math.sqrt(n);
		if (squre * squre == n) {
			return squre;
		}
		return -1;
	}
	
	public static BigInteger isSqure(BigInteger n) {
		if (n.equals(BigInteger.ONE)) {
			return n;
		}
		
		int length = n.toString().length();
		int l = length%2 == 0 ? length/2:length/2 + 1;
		BigInteger min = BigInteger.TEN.pow(l - 1);
		BigInteger max = BigInteger.TEN.pow(l).subtract(BigInteger.ONE);
		
		while (true) {
			if (max.subtract(min).compareTo(BigInteger.ONE) == 0) {
				if (max.subtract(min).compareTo(BigInteger.ONE) == 0) {
					if (min.pow(2).compareTo(n) == 0) {
						return min;
					}
					
					if (max.pow(2).compareTo(n) == 0) {
						return max;
					}	
				}
				
				return BigInteger.ZERO;
			}
			
			BigInteger middle = min.add(max).divide(new BigInteger(("2")));
			BigInteger power = middle.pow(2);
			
			 
			if (power.compareTo(n) == 0) {
				return middle;
			} else if (power.compareTo(n) > 0) {
				max = middle;
			} else if (power.compareTo(n) < 0) {
				min = middle;
			}
		}		
	}
	
	public static long gcd(long a, long b) {
		if (b == 0) {
			return a;
		}
		
		long r = a % b;
		return gcd(b, r);
	}
	
	public static long phi(long x) {
		List<Long> primes = Util.primeFactor2(x);
		for (Long p : primes) {
			x /= p;
			x *= (p - 1);
		}
		return x;		
	}
}